#ifndef __BITREE_H
#define __BITREE_H

#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
#include <cstdlib>
using namespace std;

template <typename T, typename K>
class _bitree
{
public:
	K key;
    T *lchild;
    T *rchild;
	_bitree()
	{
		lchild = rchild = NULL;
	}
};

template <typename T>
void bitree_init(T *&rt)
{
    rt = NULL;
}

template <typename K>
void input_bitree(const char *filename, vector<K> &pre, vector<K> &in)
{
	int n;
	ifstream input;

    input.open(filename);
    if (!input){
        cerr << "'" << filename << "' can not be opened." << endl;
        exit(-1);
    }
    input >> n;
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        pre.push_back(t);
    }
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        in.push_back(t);
    }

	input.close();
}

template <typename T, typename K>
T* _bitree_create(vector<K> &pre, int pl, int ph, vector<K> &in, int il, int ih)
{
    T *rt;
    int i;

    assert(ph-pl == ih-il);
    if (ph < pl) return NULL;
    for (i = il; i <= ih; i++)
        if (in[i] == pre[pl]) break;
    assert(i <= ih);
    rt = new T;
    assert(rt);
    rt->key = pre[pl];
    rt->lchild = _bitree_create<T,K>(pre, pl+1, pl+i-il, in, il, i-1);
    rt->rchild = _bitree_create<T,K>(pre, pl+i-il+1, ph, in, i+1, ih);

    return rt;
}

template <typename T, typename K>
void bitree_create(T *&rt, const char* filename)
{
    vector<K> pre, in;

	input_bitree(filename, pre, in);
    assert(pre.size() == in.size());
    rt = _bitree_create<T,K>(pre, 0, pre.size()-1, in, 0, in.size()-1);
}

template <typename T>
void bitree_destory(T *&rt)
{
    if(!rt) return;
    bitree_destory(rt->lchild);
    bitree_destory(rt->rchild);
    delete rt;
    rt = NULL;
}

template <typename T>
void bitree_preorder(T *rt)
{
    if (!rt) return;
    cout << rt->key << " ";
    bitree_preorder(rt->lchild);
    bitree_preorder(rt->rchild);
}

template <typename T>
void bitree_inorder(T *rt)
{
    if (!rt) return;
    bitree_inorder(rt->lchild);
    cout << rt->key << " ";
    bitree_inorder(rt->rchild);
}

template <typename T>
void bitree_postorder(T *rt)
{
    if (!rt) return;
    bitree_postorder(rt->lchild);
    bitree_postorder(rt->rchild);
    cout << rt->key << " ";
}

template <typename T>
void bitree_print(T *rt)
{
    cout << "The binary tree is:" << endl;
    bitree_preorder(rt);
    cout << endl;
    bitree_inorder(rt);
    cout << endl;
    bitree_postorder(rt);
    cout << endl;
}

#endif
